A virtual machine monitor (VMM), such as a hypervisor, is a program that creates virtual machines, each with virtualized hardware resources which may be backed by underlying physical hardware resources. To virtualize memory, the VMM can implement virtual translation look-aside buffers (TLBs) that cache address translations from page tables specified by guest operating systems, much like TLBs associated with physical processors. However, some operations associated with such virtual TLBs may be costly, since virtualization may entail several layers of translations between virtual memories (such as guest and hypervisor virtual memories) and physical memories (such as guest and system physical memories). Thus, it would be advantageous to provide mechanisms that would reduce the operational costs associated with virtual TLBs.